// scaup
// (c) 2010, Normen Müller, normen.mueller@gmail.com  
// $Id: Graphs.scala 136 2010-09-25 09:32:52Z normen.mueller $
package scaup.data

/** Base graph class. 
 *  <p>An undirected graph, or graph, is a pair G = (V,E), where V is a finite set and E is a set of unordered pairs
 *  of elements of V.  The elements of V are called the nodes, or vertices, of G, the elements of E are called the
 *  edges of G.</p>  
 *  <p>An edge e = {u, v} connects nodes u and v.</p> 
 *  @author  <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 *  @version DRAFT
 */
private[data] abstract class Graph {
  /** Abstract type of graph nodes
   */
  type V <: Node
  
  abstract class Node {
    /** Edge constructor
     */
    def ->(v: V): E
    
    /** The degree of the this vertex.  
     *  <p>A degree of a vertex in an undirected graph is the number of edges touching that vertex.</p>
     */
    def degree: Int
  }
  
  /** Abstract type of graph edges
   */
  type E <: Edge
  
  abstract class Edge {
    val source: V
    val target: V
  }
  
  /** Finite set of nodes
   */
  def V: Set[V]
  
  /** Finite set of edges
   */
  def E: Set[E]
 
  /** Two nodes u and v are called adjacent if there is an edge {u,v} in G.
   */
  def adjacent(u: V, v: V) = E exists (e => e.source == u && e.target == v)
  
  /** Two edges e1 and e2 are incident if they share a common node.
   */
  def incident(e1: E, e2: E) = ((e1.source, e1.target), (e2.source, e2.target)) match {
    case ((e1s, _), (e2s, _)) if e1s == e2s => true
    case ((e1s, _), (_, e2t)) if e1s == e2t => true
    case ((_, e1t), (e2s, _)) if e1t == e2s => true
    case ((_, e1t), (_, e2t)) if e1t == e2t => true
    case _                                  => false
  }
  
  /** Trait for mixing in labels to nodes
   */
  trait NodeLabels[T] { type V <: {val label: T} }
  
  /** Trait for mixing in labels to edges
   */
  trait EdgeLabels[T] { type E <: {val label: T} }
  
  /** Trait for mixing in directions to edges 
   * @provides inDegree  The "in degree" of the specified vertex. An in degree of a vertex in a directed graph is the
   *                     number of inward directed edges from that vertex.
   *                     See <a href="http://mathworld.wolfram.com/Indegree.html">
   *                     http://mathworld.wolfram.com/Indegree.html</a>. 
   * @provides incomming The set of all edges incoming into the specified vertex. 
   * @provides outDegree The "out degree" of the specified vertex. An out degree of a vertex in a directed graph is the
   *                     number of outward directed edges from that vertex.
   *                     See <a href="http://mathworld.wolfram.com/Outdegree.html">
   *                     http://mathworld.wolfram.com/Outdegree.html</a>.
   * @provides outgoing  The set of all edges outgoing from the specified vertex.
   */
  trait Directions {
    type V <: {
      def inDegree: Int //@todo How to put ``incoming.size'' here? 
      def incoming: Set[E]
      
      def outDegree: Int //@todo How to put ``outgoing.size'' here? 
      def outgoing: Set[E]
    }
  }
}

/** A simple graph.  
 *  <p>A simple graph is an undirected graph for which at most one edge connects any two vertices, and loops are not
 *  permitted. See <a href="http://mathworld.wolfram.com/SimpleGraph.html">
 *  http://mathworld.wolfram.com/SimpleGraph.html</a>.</p>
 * @author  <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 * @version DRAFT 
 * @todo Is every simple graph a multi graph?
 */
abstract class SimpleGraph extends Graph {
  override type E <: Edge
  
  //@todo roll out to explicit ``verification'' method due to performance
  abstract class Edge extends super.Edge {
    (source, target) match {
      case (source, target) if source == target         => throw new Exception("no graph loops in none pseudo graphs")
      case (source, target) if adjacent(source, target) => throw new Exception("no multiple edges in simple graphs")
      case _                                            => 
    }
  }
}

/** A multigraph. 
 *  <p>A multigraph is a non-simple undirected graph in which no loops are permitted, but multiple edges between any
 *  two vertices are. See <a href="http://mathworld.wolfram.com/Multigraph.html">
 *  http://mathworld.wolfram.com/Multigraph.html</a>.</p> 
 *  @author  <a href="mailto:normen.mueller@googlemail.com">Normen M\u00FCller</a>
 *  @version DRAFT
 */
abstract class MultiGraph extends Graph {
  override type E <: Edge
  
  //@todo roll out to explicit ``verification'' method due to performance
  abstract class Edge extends super.Edge {
    (source, target) match {
      case (source, target) if source == target => throw new Exception("no graph loops in none pseudo graphs")
      case _                                    => 
    }
  }
}
